package com.cf.r1049;

import java.io.*;
import java.util.*;

public class c {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            solve();
        }
        out.flush();
        out.close();
        br.close();
    }

    static void solve() throws IOException {
        int n = Integer.parseInt(br.readLine());
        long[] a = new long[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        long altSum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) altSum += a[i];
            else altSum -= a[i];
        }

        // 2. 维护变量
        long maxDelta = Long.MIN_VALUE;
        long minDelta = Long.MAX_VALUE;

        long bestOddForMax = Long.MIN_VALUE; // max(-i - 2*a[i]) over odd i
        long bestOddForMin = Long.MAX_VALUE; // min(-i - 2*a[i]) over odd i
        long bestEvenForMax = Long.MIN_VALUE; // max(-i + 2*a[i]) over even i
        long bestEvenForMin = Long.MAX_VALUE; // min(-i + 2*a[i]) over even i

        // 3. 扫描
        for (int j = 1; j <= n; j++) {
            long aj = a[j];
            if (j % 2 == 0) { // j 偶 -> 配对奇 i
                if (bestOddForMax != Long.MIN_VALUE) {
                    long cand = (j + 2L * aj) + bestOddForMax;
                    maxDelta = Math.max(maxDelta, cand);
                }
                if (bestOddForMin != Long.MAX_VALUE) {
                    long cand2 = (j + 2L * aj) + bestOddForMin;
                    minDelta = Math.min(minDelta, cand2);
                }
                // 更新偶数 key
                bestEvenForMax = Math.max(bestEvenForMax, -j + 2L * aj);
                bestEvenForMin = Math.min(bestEvenForMin, -j + 2L * aj);
            } else { // j 奇 -> 配对偶 i
                if (bestEvenForMax != Long.MIN_VALUE) {
                    long cand = (j - 2L * aj) + bestEvenForMax;
                    maxDelta = Math.max(maxDelta, cand);
                }
                if (bestEvenForMin != Long.MAX_VALUE) {
                    long cand2 = (j - 2L * aj) + bestEvenForMin;
                    minDelta = Math.min(minDelta, cand2);
                }
                // 更新奇数 key
                bestOddForMax = Math.max(bestOddForMax, -j - 2L * aj);
                bestOddForMin = Math.min(bestOddForMin, -j - 2L * aj);
            }
        }

        // 4. 同奇偶最远距离
        int firstOdd = -1, lastOdd = -1;
        int firstEven = -1, lastEven = -1;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) {
                if (firstEven == -1) firstEven = i;
                lastEven = i;
            } else {
                if (firstOdd == -1) firstOdd = i;
                lastOdd = i;
            }
        }
        long maxSameParityDiff = 0;
        if (firstOdd != -1 && lastOdd != -1) {
            maxSameParityDiff = Math.max(maxSameParityDiff, lastOdd - firstOdd);
        }
        if (firstEven != -1 && lastEven != -1) {
            maxSameParityDiff = Math.max(maxSameParityDiff, lastEven - firstEven);
        }

        // 5. Alice 第一手能拉动的最大增量
        long bestDelta = 0;
        if (maxDelta != Long.MIN_VALUE) {
            bestDelta = Math.max(bestDelta, maxDelta);
        }
        if (maxSameParityDiff > 0) {
            bestDelta = Math.max(bestDelta, maxSameParityDiff);
        }

        long ans = Math.max(altSum, altSum + bestDelta);
        out.println(ans);
    }
}
